package leetcode.editor.cn;

//给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。 
//
// 岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。 
//
// 
// 
// 你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。 
// 
// 
//
// 返回必须翻转的 0 的最小数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [[0,1],[1,0]]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
//输出：2
// 
//
// 示例 3： 
//
// 
//输入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// n == grid.length == grid[i].length 
// 2 <= n <= 100 
// grid[i][j] 为 0 或 1 
// grid 中恰有两个岛 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 数组 矩阵 👍 385 👎 0

import java.util.LinkedList;
import java.util.Queue;

//Java：【934】 - 最短的桥
public class LeetCode_934_ShortestBridge{
    public static void main(String[] args) {
        Solution solution = new LeetCode_934_ShortestBridge().new Solution();
                // TO TEST
        int i = solution.shortestBridge(new int[][]{{0,0,1,0,1},{0,1,1,0,1},{0,1,0,0,1},{0,0,0,0,0},{0,0,0,0,0}});
        System.out.println(i);
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        int[] dx = new int[]{1,0,-1,0};
        int[] dy = new int[]{0,1,0,-1};
        public int shortestBridge(int[][] grid) {
            int n = grid.length;
            // 标记第一座岛
            Queue<int[]> queue = new LinkedList<>();
            boolean flag = false;
            for(int i=0;i<n && !flag;i++){

                for(int j=0;j<n && !flag;j++){
                    if(grid[i][j] == 1){
                        dfs(grid, i, j, queue);
                        flag = true;
                    }

                }
            }

            // 从靠岸点开始bfs
            while(!queue.isEmpty()){
                int[] cur = queue.remove();
                for(int i=0;i<4;i++){
                    int x = cur[0]+dx[i];
                    int y = cur[1]+dy[i];
                    if(x<0 || x>=n || y<0 || y>=n) continue;
                    if(grid[x][y] == 1) return grid[cur[0]][cur[1]]-1;
                    else if(grid[x][y]==0){
                        grid[x][y] = grid[cur[0]][cur[1]] +1;
                        queue.add(new int[]{x,y});
                    }
                }
            }

            return 1;
        }

        public void dfs(int[][] grid, int x, int y, Queue<int[]> queue){
            int n = grid.length;
            if(x<0 || x>=n || y<0 || y>=n || grid[x][y]==-1 || grid[x][y]==2) return;
            if(grid[x][y] == 0) {
                grid[x][y] = 2; // 靠岸点
                queue.add(new int[]{x,y});
                return;
            }
            grid[x][y] = -1;
            for(int i=0;i<4;i++){
                dfs(grid, x+dx[i], y+dy[i], queue);
            }
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}
